package leetcode.editor.cn.q1_300.q;

import java.util.Arrays;

/**
 * @author qidi
 * @date 2021-11-11 10:29:24
 */
class Q0034_FindFirstAndLastPositionOfElementInSortedArray {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            if (nums.length == 0 || target < nums[0] && target > nums[nums.length - 1]) return new int[]{-1, -1};

            if (nums.length == 1) {
                if (nums[0] == target) {
                    return new int[]{0, 0};
                } else {
                    return new int[]{-1, -1};
                }
            }

            int l = 0;
            int r = nums.length - 1;
            int m = l + ((r - l) >> 1);
            while (l < r) {
                if (nums[l] == target) return getRange(nums, l);
                if (nums[m] == target) return getRange(nums, m);
                if (nums[r] == target) return getRange(nums, r);

                if (target > nums[m]) {
                    l = m + 1;
                    r--;
                } else {
                    l++;
                    r = m - 1;
                }
            }

            return new int[]{-1, -1};
        }

        private int[] getRange(int[] nums, int i) {
            int l = i, r = i;
            while (l > 0) {
                if (nums[l - 1] == nums[i]) {
                    l--;
                } else {
                    break;
                }
            }
            while (r < nums.length - 1) {
                if (nums[r + 1] == nums[i]) {
                    r++;
                } else {
                    break;
                }
            }

            return new int[]{l, r};
        }


    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0034_FindFirstAndLastPositionOfElementInSortedArray().new Solution();
//        System.out.println(Arrays.toString(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6)));
//        System.out.println(Arrays.toString(solution.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)));
        System.out.println(Arrays.toString(solution.searchRange(new int[]{1}, 1)));
        System.out.println(Arrays.toString(solution.searchRange(new int[]{1, 1}, 1)));
    }
}